#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;




int subarraySum(vector<int>& nums, int k) {
    // int n=nums.size();
    // int fast=0, slow=0;
    // int t=0;
    // for(slow=0; slow<n; slow++){
    //     int sum=0;
    //     sum+=nums[slow];
    //     for(fast=slow; fast<n; fast++){
    //         if(fast==slow){
    //             if(nums[fast]==k)
    //             {t++;}
    //         }else{
    //             sum+=nums[fast];
    //             if(sum==k){
    //                 t++;
    //             }
    //         }

    //     }
    // }
    // return t;
    unordered_map<int, int> mp;
    mp[0] = 1;
    int count = 0, pre = 0;
    for (auto& x : nums) {
        pre += x;
        if (mp.find(pre - k) != mp.end()) {
            count += mp[pre - k];
        }
        mp[pre]++;
    }
    return count;
}

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    // int n = nums.size();
    // priority_queue<pair<int, int>> q;
    // for (int i = 0; i < k; ++i) {
    //     q.emplace(nums[i], i);
    // }
    // vector<int> ans = {q.top().first};
    // for (int i = k; i < n; ++i) {
    //     q.emplace(nums[i], i);
    //     while (q.top().second <= i - k) {
    //         q.pop();
    //     }
    //     ans.push_back(q.top().first);
    // }
    // return ans;
    int n = nums.size();
    vector<int> prefixMax(n), suffixMax(n);
    for (int i = 0; i < n; ++i) {
        if (i % k == 0) {
            prefixMax[i] = nums[i];
        }
        else {
            prefixMax[i] = max(prefixMax[i - 1], nums[i]);
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        if (i == n - 1 || (i + 1) % k == 0) {
            suffixMax[i] = nums[i];
        }
        else {
            suffixMax[i] = max(suffixMax[i + 1], nums[i]);
        }
    }

    vector<int> ans;
    for (int i = 0; i <= n - k; ++i) {
        ans.push_back(max(suffixMax[i], prefixMax[i + k - 1]));
    }
    return ans;
}


int main()
{
    vector<int> v = {3,4,7,2,1,5,6,8,3,1};
    subarraySum(v, 7);
    return 0;
}